package 回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 *                     []
 *          []                   [1]                    :选不选1
 *     []      [2]          [1]        [1,2]            :选不选2
 *  []  [3] [2]  [2,3]   [1] [1,3]  [1,2] [1,2,3]       :选不选3
 */

public class LeetCode78_子集 {
    public List<List<Integer>> subset(int[] nums) {
        // 这个是可以看作是树的深度，走到最底层才输出
        int len = nums.length;

        List<List<Integer>> res = new ArrayList<>();
        if(len == 0) {
            return res;
        }
        // 路径变量
        Deque<Integer> path = new ArrayDeque<>();
        dfs(nums, len, 0, path,res);
        return res;
    }

    private void dfs(int[] nums, int len, int index,
                     Deque<Integer> path, List<List<Integer>> res) {
        if(index == len) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 不选择这个元素，直接进入下一层，
        dfs(nums, len, index + 1, path, res);
        path.addLast(nums[index]); // 考虑这个元素，加入它
        // 选择这个元素，进入下一层
        dfs(nums, len, index + 1, path, res);
        path.removeLast();
    }
}













